#include "my_malloc.h"

/* 
holds a pointer to the "head" of the list of all memory segments alloced by mmap.
this is the address of the first memory segment allocated and in its header there's a pointer to next one and so on.
*/
void* memHead = NULL;

pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;

/* 
fills the segment's headerr with the given parameters:
1) size of the segment (not including the header)
2) pointer to the previous free segment (in case this segment)
3) pointer to the next free segment (in case this segment)
*/
void fillHeader(char *add, size_t size, /*char free,*/ char *prev, char *next) {
	size_t ssize;
	/* fill the segment's size */
	memcpy (add, (char*)&(size), sizeof(size_t));
	/* fill the prev_free and next_free - not relevent for an allocated segment (NULL in that case) */
	memcpy (add + NEXT_FREE, (char*)&(next), sizeof(void*));
	memcpy (add + PREV_FREE, (char*)&(prev), sizeof(void*));
	/* fill the footer of the segment */
	memcpy ((char*)&ssize, add, sizeof(size_t));
}

/* 
fills a memory segment header with the given parameters:
1) size of the segment (not including the header)
2) pointer to the head of the "free list" (the smallest free segment)
*/
void fillMemHeader(char *add, size_t size, char *free) {
	char *null = NULL; 
	/* fill the pointer to the first free block (the smallest) - only used when this is the first memory segment allocated (memHead) */
	memcpy (add, (char*)&(free), sizeof(void*));
	/* fill the size of the memory segment - used to free it */
	memcpy (add + SIZE, (char*)&(size), sizeof(size_t));
	/* fill the pointer to the next memory segment - always NULL at first */
	memcpy (add + NEXT, (char*)&(null), sizeof(void*));
}

/* removes a segment from the "free list" */
void removeFree(void *add) {
	char *prev, *next, *first;
	/* gets pointers to its neighbors */
	memcpy((char*)&(prev), (char*)add + PREV_FREE, sizeof(void*)); 
	memcpy((char*)&(next), (char*)add + NEXT_FREE, sizeof(void*)); 
	/* if they are not NULL update them */
	if (prev != NULL) memcpy(prev + NEXT_FREE, (char*)&(next), sizeof(void*));
	if (next != NULL) memcpy(next + PREV_FREE, (char*)&(prev), sizeof(void*));
	/* check if this is the first free segment, pointed by memHead, and if so, update memHead as well */
	memcpy((char*)&(first), (char*)memHead, sizeof(void*)); 
	if (add == first) {
		memcpy((char*)memHead, (char*)&(next), sizeof(void*));
	}
}

/* creates a free segment and add it to the "free list" */
void createFree(void *add, size_t size) {
	void *curr, *next, *null = NULL;
	size_t nextSize, currSize;
	
	/* insert to the free list, at the right place according to the size */
	/* get a ptr to the address of the first and second free spaces (the smallest) */
	memcpy((char*)&(curr), (char*)memHead, sizeof(void*));
	if (curr == NULL) {
		/* the "free list" is empty */
		/* make this segment the head of the "free list" and its neighbors are NULL */
		memcpy((char*)add + NEXT_FREE, (char*)&(null), sizeof(void*));
		memcpy((char*)add + PREV_FREE, (char*)&(null), sizeof(void*));
		memcpy((char*)memHead, (char*)&(add), sizeof(void*));
	} 
	else {
		/* the "free list" is not empty */
		/* get the size of the first segment in the list */
		memcpy((char*)&(currSize), (char*)curr, sizeof(size_t));
		if (currSize > size) {
			/* this block should be the head of the "free list" */
			memcpy((char*)add + NEXT_FREE, (char*)&(curr), sizeof(void*));
			memcpy((char*)add + PREV_FREE, (char*)&(null), sizeof(void*));
			memcpy((char*)curr + PREV_FREE, (char*)&(add), sizeof(void*));
			/* also update the memory segment holding the head of the "free list" */
			memcpy((char*)memHead, (char*)&(add), sizeof(void*));
		} 
		else {
			memcpy((char*)&(next), (char*)curr + NEXT_FREE, sizeof(void*));
			/* move on the list untill next >= size (find the right place to insert, according to the size) */
			while (next != NULL) {
				memcpy((char*)&(nextSize), (char*)next, sizeof(size_t));
				if (nextSize >= size) break;
				/* increment the pointers */
				curr = next;
				memcpy((char*)&(next), (char*)next + NEXT_FREE, sizeof(void*)); /* ??? */  
			}
			/* update the free segement and its "new neighbors" */
			memcpy((char*)add + NEXT_FREE, (char*)&(next), sizeof(void*));
			memcpy((char*)add + PREV_FREE, (char*)&(curr), sizeof(void*));
			memcpy((char*)curr + NEXT_FREE, (char*)&(add), sizeof(void*));
			if (next != NULL) {
				/* this block is not the end of the list */
				memcpy((char*)next + PREV_FREE, (char*)&(add), sizeof(void*));
			}
		}
	}
}

/* allocates and initializas the first memory segment - memHead */
void initialize() {
	/* allocates memory */
	memHead = mmap(0, (size_t) MEM_SEGMENT_SIZE, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, (size_t) 0);
	if (memHead == MAP_FAILED) {
		return;
	}
	/* fill the header of the memory segment */
	/* for now, there is only one free segment inside it */
	fillMemHeader((char*)memHead, MEM_SEGMENT_SIZE, (char*)memHead + MEM_SEGMENT_HEADER_SIZE);
	/* fill the header of the free segment inside it */
	fillHeader((char*)memHead + MEM_SEGMENT_HEADER_SIZE, MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - SEGMENT_HEADER_SIZE /*- SEGMENT_FOOTER_SIZE, (char) 1*/, NULL, NULL);
}

/* creates a new memory segment, initializes it, allocates inside it the number of butes specified and returns it's address */
void* createMemSegment (size_t size) {
	void *add;
	size_t second, secondSize, restSize;
	
	if (size > (size_t) MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - SEGMENT_HEADER_SIZE ) {
		/* special case for a single very big allocation - there's no room for a second  free segment inside */
		secondSize = size + MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE;
	}
	else secondSize = MEM_SEGMENT_SIZE;
	/* allocate */
	add = mmap(0, secondSize, PROT_READ | PROT_WRITE, MAP_ANONYMOUS | MAP_SHARED, -1, 0);
	if (add == MAP_FAILED) {
		return NULL;
	}
	/* fill the header of the memory segment */
	/* for now, there is no free segment - only one segment which is full */
	fillMemHeader((char*)add, secondSize, NULL);

	if (secondSize == MEM_SEGMENT_SIZE) {
		/* check to see if there's enough room for a second block */
		if (MEM_SEGMENT_SIZE > MEM_SEGMENT_HEADER_SIZE + size + 2*SEGMENT_HEADER_SIZE ) {
			restSize = MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - size - 2*SEGMENT_HEADER_SIZE ;
			/* create a new free block from the rest and add it to the free list */
			second = MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE + size ;
			createFree((char*)add + second, restSize);
			/* fill the size inside the header of the free segment */
			memcpy ((char*)add + second, (char*)&(restSize), sizeof(size_t));

			/* fill the header of the first (allocated) segment inside */
			fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, size,  NULL, NULL);
		}
		else {
			/* fill the header of the first (allocated) segment inside */
			fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, MEM_SEGMENT_SIZE - MEM_SEGMENT_HEADER_SIZE - size - SEGMENT_HEADER_SIZE , NULL, NULL);
		}
	}
	else {
		/* fill the header of the first (allocated) segment inside */
		fillHeader((char*)add + MEM_SEGMENT_HEADER_SIZE, size,  NULL, NULL);
	}
	return add;
}

/* receives a free block address, allocates the needed space inside it and updates the "free list" list */
void allocateAndUpdate (void *add, size_t size, size_t blockSize) {
	size_t restSize = blockSize;
	/* remove the block from the "free list" */
	removeFree(add);
	
	/* check to see if there's enough room left (after the allocation) to create a new free block from the rest */
	if (restSize > size + SEGMENT_HEADER_SIZE ) {
		restSize -= size + SEGMENT_HEADER_SIZE ;
		/* create a new free block from the rest and add it to the "free list" */
		createFree((char*)add + size + SEGMENT_HEADER_SIZE, restSize);
		pthread_mutex_unlock(&mutex1);
		/* fill the size inside the header of the new block */
		memcpy ((char*)add + size + SEGMENT_HEADER_SIZE, (char*)&(restSize), sizeof(size_t));
		/* update the header */
		fillHeader((char*)add, size, NULL, NULL);
	}
	else {
		pthread_mutex_unlock(&mutex1);
	}
}

void* myMalloc (size_t size) {
	void *add, *memTmp, *memNext;
	size_t blockSize;
	pthread_mutex_lock(&mutex1);
	if (memHead == NULL) {
		initialize();
	}
	/* finds and allocates a free segment (at the smallest size possible that is larger then size) and returns its address */
	/* get a pointer to the address of the first free block (the smallest) */
	memcpy((char*)&(add), (char*)memHead, sizeof(void*)); 
	/* find the smallest free block that is big eanough for the allocation */
	while (add != NULL) {
		memcpy((char*)&(blockSize), (char*)add, sizeof(size_t));
		if (blockSize >= size) break;
		/* move to the next free block */
		memcpy((char*)&(add), (char*)add + NEXT_FREE, sizeof(void*)); 
	}
	if (add == NULL) {
		/* there is no free block - allocate a new memory segment */
		add = createMemSegment(size);
		if (add == NULL) {
			pthread_mutex_unlock(&mutex1);
			return NULL;
		}
		/* reach the end of the memory segments list */
		memTmp = memHead;
		memcpy((char*)&(memNext), (char*)memTmp + NEXT, sizeof(void*)); 
		while (memNext != NULL) {
			memTmp = memNext;
			memcpy((char*)&(memNext), (char*)memTmp + NEXT, sizeof(void*)); 
		}
		/* link the last memory segment to the new one, we just allocated */
		memcpy ((char*)memTmp + NEXT, (char*)&(add), sizeof(void*));
		pthread_mutex_unlock(&mutex1);
		return (void*) ((char*)add + MEM_SEGMENT_HEADER_SIZE + SEGMENT_HEADER_SIZE);
	}
	/* we found a free block that's big enough */
	allocateAndUpdate(add, size, blockSize);
	return (void*) ((char*)add + SEGMENT_HEADER_SIZE);
}

void myFree (void* add) {
	size_t size;
	memcpy((char*)&(size), (char*)add - SEGMENT_HEADER_SIZE, sizeof(size_t));
	pthread_mutex_lock(&mutex1);
	createFree((char*)add - SEGMENT_HEADER_SIZE, size);
	pthread_mutex_unlock(&mutex1);
	/* fill the size inside the header */
	memcpy ((char*)add - SEGMENT_HEADER_SIZE, (char*)&(size), sizeof(size_t));
}

/* frees all the memory segments the were allocated */
void freeAll() {
	void *curr, *next;
	size_t size;
	pthread_mutex_lock(&mutex1);
	curr = memHead;
	while (curr != NULL) {
		memcpy((char*)&(size), (char*)curr + SIZE, sizeof(size_t));
		memcpy((char*)&(next), (char*)curr + NEXT, sizeof(void*));
		munmap(curr, size);
		curr = next;
	}
	pthread_mutex_unlock(&mutex1);
}
